package array;


import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 找出数组中的重复数字,输出该重复数字 长度为n的数组，所有元素范围都在0到n-1里
 */
public class FindRepeatElement {

  /**
   * hash的方法，时间复杂度为o（n），但是空间复杂度高了
   */
  public void findRepeatCount(int[] array) {

    if (array == null || array.length <= 0) {
      System.out.println("数组为null或数组的长度<=0");
      return;
    }

    for (int i = 0; i < array.length; i++) {
      if (array[i] < 0 || array[i] > array.length - 1) {
        System.out.println("数组中存在元素范围不在0-" + (array.length - 1) + "的元素");
      }
    }
    Map<Integer, Integer> map = new HashMap();
    Set<Integer> set = new HashSet();
    for (int i = 0; i < array.length; i++) {
      if (!map.values().contains(array[i])) {
        map.put(i, array[i]);
      } else {
        set.add(array[i]);
      }
    }

    if (set.isEmpty()) {
      System.out.println("不存在重复元素");
    } else {
      for (int i : set) {
        System.out.println("重复的数字是" + i);
      }
    }
  }

  /**
   * 时间复杂度o（n） 空间复杂度o（1）的最优解
   */
  public void findRepeatCount2(int[] array) {
    if (array == null || array.length <= 0) {
      System.out.println("数组为null或数组的长度<=0");
      return;
    }

    for (int i = 0; i < array.length; i++) {
      if (array[i] < 0 || array[i] > array.length - 1) {
        System.out.println("数组中存在元素范围不在0-" + (array.length - 1) + "的元素");
      }
    }

    //保存找到的重复数字
    Set<Integer> set = new HashSet();

    for (int i = 0; i < array.length; i++) {
      //如果当前下标的值和当前下标相同，则跳过，不同的话则和array【当前下标的值进行判断】
      if (array[i] != i) {
        //相同的话证明重复
        int value = array[i];
        if (array[i] == array[value]) {
          set.add(array[i]);
        } else {//不同的话就互换
          int temp = array[i];
          array[i] = array[value];
          array[value] = temp;
        }
      }
    }

    if (set.isEmpty()) {
      System.out.println("不存在重复元素");
    } else {
      for (int i : set) {
        System.out.println("重复的数字是" + i);
      }
    }


  }


  public static void main(String args[]) {
    FindRepeatElement FindRepeatElement = new FindRepeatElement();
    int[] array = new int[]{2, 3, 1, 1, 2, 5, 3};
    FindRepeatElement.findRepeatCount2(array);
    FindRepeatElement.findRepeatCount2(null);
    FindRepeatElement.findRepeatCount2(new int[]{});
    FindRepeatElement.findRepeatCount2(new int[]{0, 1, 2, 3, 4});

  }
}
